package 程序员面试金典;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 面试题 03.02. 栈的最小值
 * 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
 *
 *
 * 示例：
 *
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.getMin();   --> 返回 -2.
 */
class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;
    // 构造器
    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        // 这一步很关键:就是让首个加入的x也可以顺利加入minStack
        minStack.addFirst(Integer.MAX_VALUE);
    }

    // 往栈顶加入元素
    public void push(int x) {
        // 常规栈直接加入,最小栈加入当前栈中最小值(统一以队头为栈顶)
        stack.addFirst(x);
        // 求出当前栈中的最小值
        int min = Math.min(minStack.peekFirst(), x);
        minStack.addFirst(min);
    }

    // 弹出栈顶元素(不返回)
    public void pop() {
        // 常规栈直接弹出,最小栈同步更新
        int pop = stack.pollFirst();
        // 这里无论pop是何止都要弹出minStack栈顶,因为两个栈的个数总是一致的
        minStack.pollFirst();
    }

    // 获取栈顶元素(不弹出)
    public int top() {
        return stack.peekFirst();
    }

    // 获取栈中最小值
    public int getMin() {
        return minStack.peekFirst();
    }
}

public class T03_02 {
}

